package sort.quickSort;

/**
 * @Author: zhang
 * @Description: 快排递归优化-三数取中法
 * @Date: Created in 2:07 2019/9/20
 */
public class ThreeWaySortTest {
    public static void main(String[] args) {
        int[] arrays = new int[]{5, 1, 7, 4, 8, 9, 2, 3, 6, 0};
        ThreeWaySort(arrays, 0, arrays.length - 1);
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + " ");
        }
    }

    public static void ThreeWaySort(int[] a, int low, int high) {
        //已经排序完成
        if (low >= high) {
            return;
        }
        //三数取中调整基准值
        medianOfThree(a, low, high);
        int pivotIndex = partition(a,low,high);
        //开始递归(左边/右边)
        ThreeWaySort(a, low, pivotIndex - 1);
        ThreeWaySort(a, pivotIndex + 1, high);
    }

    public static int partition(int[] a, int left, int right) {
        int pivot = a[left];
        while (left < right) {
            //从后向前找比基准小的值
            while (left < right && a[right] >= pivot) {
                right--;
            }
            a[left] = a[right];
            //从前向后找比基准大的值
            while (left < right && a[left] <= pivot) {
                left++;
            }
            a[right] = a[left];
        }
        //把基准放回数组中
        a[left] = pivot;
        //返回基准的下标
        return left;
    }

    //优化-三数取中
    //调整为：mid <= low <= high
    public static void medianOfThree(int[] a, int low, int high) {
        int mid = (low + high) / 2;
            if (a[mid] > a[low]) {
                swap(a, a[mid], a[low]);
            }
            if (a[mid] > a[high]) {
                swap(a, a[mid], a[high]);
            }
            if (a[low] > a[high]) {
                swap(a, a[low], a[high]);
        }
    }

    public static void swap(int[] a, int i, int j) {
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
}
